package com.sheng.leetcode.year2023.month06.day15;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2023/06/15
 * <p>
 * 1177. 构建回文串检测<p>
 * <p>
 * 给你一个字符串 s，请你对 s 的子串进行检测。<p>
 * 每次检测，待检子串都可以表示为 queries[i] = [left, right, k]。<p>
 * 我们可以 重新排列 子串 s[left], ..., s[right]，并从中选择 最多 k 项替换成任何小写英文字母。<p>
 * 如果在上述检测过程中，子串可以变成回文形式的字符串，那么检测结果为 true，否则结果为 false。<p>
 * 返回答案数组 answer[]，其中 answer[i] 是第 i 个待检子串 queries[i] 的检测结果。<p>
 * 注意：在替换时，子串中的每个字母都必须作为 独立的 项进行计数，也就是说，<p>
 * 如果 s[left..right] = "aaa" 且 k = 2，我们只能替换其中的两个字母。<p>
 * （另外，任何检测都不会修改原始字符串 s，可以认为每次检测都是独立的）<p>
 * <p>
 * 示例：<p>
 * 输入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]<p>
 * 输出：[true,false,false,true,true]<p>
 * 解释：<p>
 * queries[0] : 子串 = "d"，回文。<p>
 * queries[1] : 子串 = "bc"，不是回文。<p>
 * queries[2] : 子串 = "abcd"，只替换 1 个字符是变不成回文串的。<p>
 * queries[3] : 子串 = "abcd"，可以变成回文的 "abba"。 也可以变成 "baab"，先重新排序变成 "bacd"，然后把 "cd" 替换为 "ab"。<p>
 * queries[4] : 子串 = "abcda"，可以变成回文的 "abcba"。<p>
 * <p>
 * 提示：<p>
 * 1 <= s.length, queries.length <= 10^5<p>
 * 0 <= queries[i][0] <= queries[i][1] < s.length<p>
 * 0 <= queries[i][2] <= s.length<p>
 * s 中只有小写英文字母<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/can-make-palindrome-from-substring">1177. 构建回文串检测</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1177 {

    @Test
    public void test01() {
        String s = "abcda";
        int[][] queries = {{3, 3, 0}, {1, 2, 0}, {0, 3, 1}, {0, 3, 2}, {0, 4, 1}};
        System.out.println(new Solution().canMakePaliQueries(s, queries));
    }
}

class Solution {

    int[][] ss;

    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        // queries[i] = {x, y, z} 代表，从字符串中截取索引为 x ~ y 的一个子串，随意排序，最多可以变成 z 次，要求变更后为一个回文串
        int n = s.length();
        ss = new int[n + 1][26];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 26; j++) {
                ss[i][j] = ss[i - 1][j];
            }
            ss[i][s.charAt(i - 1) - 'a']++;
        }
        List<Boolean> list = new ArrayList<>();
        for (int[] query : queries) {
            // 判断子串打乱顺序并且替换过后是否满足回文串
            list.add(judge(query[0], query[1], query[2]));
        }
        return list;
    }

    public boolean judge(int x, int y, int k) {
        // 每个字符的数量除以 2 之后的余数相加减去 k 之后，要求小于等于 1
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += (ss[y + 1][i] - ss[x][i]) & 1;
        }
        return ans - 2 * k <= 1;
    }
}
